The present invention is a continuation-in-part of co-pending U.S. patent application Ser. No. 08/743,484 now U.S. Pat. No. 6,134,627, filed Nov. 4, 1996, and claims priority of copending provisional U.S. patent application Ser. No. 60/057,050, filed Aug. 27, 1997, which are incorporated herein by reference in their entirety.
1. Field of Invention
The invention relates generally to methods and apparatus for locking and unlocking objects in an object-based system. More particularly, the invention relates to methods and apparatus for enabling multiple concurrent threads to operate synchronously, and efficiently, in an object-based system.
2. Description of Relevant Art
An object generally includes a set of operations and a state that remembers the effect of the operations. Since an object has some memory capability, an object differs from a function, which has substantially no memory capability. For example, a value returned by an operation associated with an object is dependent upon the state of the object as well as the arguments to the operation. As such, each invocation of an object may have a different result. In contrast, a value returned by a function is typically dependent only on the arguments to the function. Accordingly, for a given set of arguments, each invocation of a function will have the same result.
Within an object-based environment, threads are often used to satisfy requests for services. A thread may be thought of as a xe2x80x9csketch padxe2x80x9d of storage resources, and is essentially a single sequential flow of control within a computer program. In general, a thread, or a xe2x80x9cthread of control,xe2x80x9d is a sequence of central processing unit (CPU) instructions or programming language statements that may be independently executed. Each thread has its own execution stack on which method activations reside. As will be appreciated by those skilled in the art, when a method is activated with respect to a thread, an activation is xe2x80x9cpushedxe2x80x9d on the execution stack of the thread. When the method returns, or is deactivated, the activation is xe2x80x9cpoppedxe2x80x9d from the execution stack. Since an activation of one method may activate another method, an execution stack operates in a first-in-last-out manner.
Threads may generally be either xe2x80x9ccooperativexe2x80x9d or xe2x80x9cconcurrent.xe2x80x9d Threads are considered to be cooperative when a single thread maintains complete control, e.g., control of a computational resource such as a processor or a process, until the thread voluntarily relinquishes control. Concurrent threads, on the other hand, are arranged such that although a thread may also voluntarily relinquish control, other threads may essentially cause the thread to involuntarily relinquish control.
In a concurrent threading model, multiple threads are allowed to execute independently of one another. Rather than being cooperatively scheduled like cooperative threads, concurrent threads are preemptively scheduled. That is, a computation by a given concurrent thread may be preempted at any point in time by an outside entity such as another concurrent thread, e.g., a scheduler, or the operating system. Thread preemption may occur because of meaningful events in the execution of a program. By way of example, a meaningful event may be when a thread""s priority is programmatically raised to be higher than that of a currently running thread. Alternatively, thread preemption may occur because of artificially induced events such as the elapsing of a particular interval of time.
During the execution of an object-based program, a thread may attempt to execute operations which involve multiple objects. On the other hand, multiple threads may attempt to execute operations which involve a single object. Frequently, only one thread is allowed to invoke one of some number of operations, i.e., synchronized operations, that involve a particular object at any given time. That is, only one thread may be allowed to execute a synchronized operation on a particular object at one time. A synchronized operation, e.g., a synchronized method, is block-structured in that it requires that the thread invoking the method to first synchronize with the object that the method is invoked on, and desynchronize with that object when the method returns. Synchronizing a thread with an object generally entails controlling access to the object using a synchronization construct before invoking the method.
In addition to the synchronized operations defined on a given object, there may be some number of non-synchronized operations defined on that object. Non-synchronized operations are not prevented from being simultaneously executed on a given object by more than one thread. Several non-synchronized operations may be executed at once on a given object, and one or more non-synchronized operations may be executed at the same time as a synchronized operation.
Since a concurrent thread is not able to predict when it will be forced to relinquish control, synchronization constructs such as locks, mutexes, semaphores, and monitors may be used to control access to shared resources during periods in which allowing a thread to operate on shared resources would be inappropriate. By way of example, in order to prevent more than one thread from operating on an object at any particular time, objects are often provided with locks. The locks are arranged such that only the thread that has possession of the lock for an object is permitted to execute a method on that object. With respect to FIG. 1, a process of acquiring an object lock will be described. The process of acquiring an object lock begins at step 104 where a thread obtains the object on which the thread wishes to operate. In general, the object on which the thread intends to operate has an associated object lock. Then, in step 106, a determination is made regarding whether the object is locked. That is, a determination is made regarding whether the object lock associated with the object is held by another thread, e.g., a thread that is currently operating on the object.
If the determination in step 106 is that the object is not locked, then the thread acquires the object lock in step 108. Alternatively, if the object is locked, then the thread waits for the object to be unlocked in step 110. Once the object is unlocked, process flow moves from step 110 to step 108 where the object is locked by the thread.
As previously mentioned, a thread is permitted to execute a synchronized operation on an object if it successfully acquires the lock on the object. While one thread holds the lock on an object, other threads may be allowed to attempt to execute additional synchronization operations on the object, and may execute non-synchronized operations on the object. Thread synchronization is a process by which threads may interact to check the status of objects, whether the objects are locked or unlocked, while allowing only the thread which holds an object lock to execute synchronized operations on the locked object. Thread synchronization also enables threads to obtain and remove object locks.
When threads are synchronized, in order to make certain that only the thread that possesses an object lock is allowed to operate on a locked object, synchronization constructs are generally provided. FIG. 2 is a diagrammatic representation of the interface between a thread, an object, and a synchronization construct in an object-based system. A thread 202 attempts to execute a synchronized operation on an object 204. In order for thread 202 to execute the synchronized operation on object 204, thread 202 must first obtain the object lock for object 204.
When thread 202 attempts to execute a synchronized operation on object 204, a synchronization construct 206 which is associated with object 204 is obtained. In general, object 204 is dynamically associated with a synchronization construct, as for example synchronization construct 206a, which is arranged to provide synchronized access to object 204. If synchronization construct 206a permits re-entrant locking of object 204, it may include a counter 208 which may be incremented to keep track of the number of times object 204 has been locked by thread 202. Synchronization construct 206a further includes an object pointer 210 that identifies object 204 or, more generally, the object with which monitor 206a is associated. Synchronization construct 206a also includes an identifier for thread 202, the thread that currently has locked synchronization construct 206a. 
A synchronization construct cache is generally a set of data structures and locks that implement a dynamic association between a synchronization construct and an object. For example, object 204 is mapped to synchronization construct 206a through a synchronization construct cache. Since synchronization constructs 206 may be of a size comparable to the size of objects, e.g., synchronization constructs 206a, 206b, 206c may require more memory space than some objects, synchronization constructs 206 are often dynamically associated with objects. Dynamically associating synchronization construct 206a with object 204 prevents object 204 from being associated with a relatively large amount of memory except when necessary, e.g., when object 204 is locked and synchronization construct 206a is in use.
Since synchronization construct 206a is not inherently associated with object 204, when thread 202 attempts to execute a synchronized operation on object 204, a search must be made to locate synchronization construct 206a. Specifically, a cache 212 of synchronization constructs 206 is searched to locate synchronization construct 206a. In general, only one synchronization construct 206 is associated with any given object 204. If a synchronization construct 206 that is associated with object 204 is not found, then a monitor 206 may be allocated using any suitable method.
Synchronization construct caches are described in more detail in U.S. patent application Ser. No. 08/569,805 now U.S. Pat. No. 5,797,004, filed Dec. 8, 1995, and U.S. patent application Ser. No. 08/832,090 now U.S. Pat. No. 5,875,461, filed Apr. 3, 1997, which are herein incorporated by reference in their entirety.
The use of monitors as synchronization constructs to track the status of objects is often relatively inefficient in that a software cache or a hash table of synchronization constructs must typically be searched in order to locate the proper monitor for use with a given object. Such searches may prove to be time-consuming, and generally utilize relatively large amounts of computer system resources. The cache of synchronization constructs, in itself, typically occupies a significant amount of computer memory. In addition, the memory management associated with allocating a monitor for an object when a suitable monitor does not already exist may be costly. Finally, as synchronization construct caches may be shared among multiple threads, they themselves may have to be locked prior to access or update, which both imposes additional costs in execution time and also introduces a source of locking contention that occurs when more than one thread wants to access the synchronization construct cache at one time.
If synchronization constructs are to support re-entrant locking, they may also require explicit counters which are used to track the number of times a given thread relocks an object that it has already locked. The implementation and maintenance of explicit counters may be relatively expensive in terms of the use of computer system resources. Further, since the synchronization construct explicitly keeps track of the thread that has locked it, the synchronization construct must be continually updated. Continually updating the synchronization construct is typically both time-consuming and expensive in terms of the consumption of computer system resources.
Although the use of synchronization constructs is generally effective in preventing concurrent execution of synchronized operations by several threads, the use of synchronization constructs is often inefficient and expensive in terms of the consumption of system resources, as previously described. Further, the space overhead associated with locking and unlocking synchronized objects is often high, while the execution speed associated with locking and unlocking may be low. Therefore, what is desired is an efficient method and apparatus for locking and unlocking objects. Specifically, what is desired is an efficient method and apparatus for keeping track of the status of an object in an object-based system that utilizes synchronized threads.
Methods and apparatus for locking and unlocking objects by threads are disclosed. According to one aspect of the present invention, a computer-implemented method for using a first thread to obtain a header value of an object includes replacing the contents of a header field of the object with a sentinel that identifies an execution stack associated with the first thread. Once the object header field contents are replaced with the sentinel, a determination is made regarding whether the object header field contents include a header value of the object, and when it is determined that the object header field contents do not include the header value of the object, a determination is made as to when the object is in the process of being studied by a second thread. In one embodiment, when it is determined that the object is not in the process of being studied by a second thread, the method involves adding the first thread to a list associated with the stack associated with the second thread. The list is arranged to indicate that the first thread is awaiting access to the object.
In another embodiment, when it is determined that the object is in the process of being studied by a second thread, the object header field contents are resolved to identify the second thread, and it is determined whether an execution priority associated with the second thread is less than an execution priority associated with the first thread. In such an embodiment, when it is determined that the second thread execution priority is less than the first thread execution priority, the method further includes boosting the second thread execution priority to match the first thread execution priority.
According to still another embodiment of the present invention, a computer-implemented method for returning a header value of an object to the header field of the object includes exchanging contents of a header field of the object for a sentinel that is arranged to identify an execution stack associated with a thread which possesses the header value of the object. The contents of the object header field are used to determine if a second thread is currently studying the object. If it is determined that the object is not being studied by the second thread, the sentinel is replaced with the header value to thereby return the header value to the object.
In one embodiment, when it is determined that the object is being studied by the second thread, the contents of the object header field are resolved to identify the second thread. Then, it is determined whether an execution priority of the second thread is less than the execution priority of the first thread. In such an embodiment, when it is determined that the second thread execution priority is less than the first thread execution priority, the method further includes boosting the second thread execution priority to the first thread execution priority to facilitate the processing of the object.
According to yet another aspect of the present invention, a computer system includes a memory and a plurality of threads, each of which has an associated stack. The computer system also includes a processor coupled to the memory, and an object that includes an object header field that contains a header value which includes information relating to the object. A first thread selected from the plurality of threads is arranged to obtain the header value and to place a first reference indicator in the object header field to identify the stack associated with the first thread. In one embodiment, a second thread selected from the plurality of threads is arranged to obtain the first reference indicator from the object header field. In such an embodiment, the second thread is also arranged to place a second reference indicator in the object header field which identifies a stack associated with the second thread.
These and other advantages of the present invention will become apparent upon reading the following detailed descriptions and studying the various figures of the drawings.